package leetcode_2701_2800;

import sun.print.SunMinMaxPage;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeeCode_2744 {
    public static void main(String[] args) {
        System.out.println(minimumFuelCost(new int[][]{{0, 1}, {0, 2}, {1, 3},{1,4}}, 5));
    }
    private static long minimumFuelCost(int[][] roads, int seats) {
        if (roads.length == 0)
            return 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] road : roads) {
            if (map.containsKey(road[0])){
                map.get(road[0]).add(road[1]);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(road[1]);
                map.put(road[0], list);
            }
            if (map.containsKey(road[1])){
                map.get(road[1]).add(road[0]);
            }else {
                List<Integer> list = new ArrayList<>();
                list.add(road[0]);
                map.put(road[1], list);
            }
        }
        long[] ans = new long[1];
        for (Integer next : map.get(0)) {
            dfs(map, next, 0, seats, ans);
        }
        return ans[0];
    }
    private static long dfs(Map<Integer, List<Integer>> map, int now, int fa, int seats, long[] ans){
        long son = 1;
        for (Integer next : map.get(now)) {
            if (next == fa)
                continue;
            son += dfs(map, next, now, seats, ans);
        }
        ans[0] += (son + seats - 1) / seats;
        return son;
    }
}
